//
// Created by REEJI2219 on 2024-09-14.
//
#include "iostream"
#include <string>

using namespace std;
typedef std::string String;
typedef std::unordered_map<char, String>  HashMap;
class HuffmanTreeNode {
public:
    char data;
    int wigth;//权重
    HuffmanTreeNode *left;
    HuffmanTreeNode *right;
    bool moved;
    HuffmanTreeNode() {
        wigth = 0;
        left = nullptr;
        right = nullptr;
        moved= false;
        data = '-';
    }
};
class HuffmanTree {
private:
    HuffmanTreeNode *root;
    HuffmanTreeNode **elementList;
    int max;
    int last;
    HashMap encodeMap;
public:
    HuffmanTree() {
        root = nullptr;
        max = 10;
        last = 0;
        elementList = new HuffmanTreeNode*[max];
    }
    void appendElemet(char data,int count) {
        HuffmanTreeNode *element = new HuffmanTreeNode();
        element->data=data;
        element->wigth=count;
        element->moved=false;
        elementList[last] = element;
        last++;
    }
    void decodeTree() {
        doDecodeTree(root,"");
    }
    void doDecodeTree(HuffmanTreeNode *node,String prefix) {
        if(node!=nullptr) {
            if(node->data!='-') {
                encodeMap[node->data]=prefix;
            }
            doDecodeTree(node->left,prefix+"0");
            doDecodeTree(node->right,prefix+"1");
        }
    }
    void printEncode() {
        for (const auto &pair : encodeMap) {
            std::cout << pair.first << " -> " << pair.second << std::endl;
        }
    }
    String encodeStr(char *chars) {
        int i=0;
        String str = "";
        while (true) {
            if(chars[i]=='\0') {
                break;
            }else {
                str = str + encodeMap[chars[i]];
                i++;
            }
        }
        return str;
    }
    void transToHuffmanTree() {
        while (true) {
            int firstMinIndex = takeAndRemoveMiniData();
            int secondMinIndex = takeAndRemoveMiniData();
            if(secondMinIndex==-1) {
                root = elementList[firstMinIndex];
                break;
            }
            HuffmanTreeNode *newRoot = new HuffmanTreeNode();
            newRoot->left= elementList[firstMinIndex];
            newRoot->right = elementList[secondMinIndex];
            newRoot->wigth= elementList[firstMinIndex]->wigth+elementList[secondMinIndex]->wigth;
            replaceMovedElement(newRoot);
        }
    }
    void printNode() {
        printNode(root);
    }
    void printNode(HuffmanTreeNode *node) {
        if(node!=nullptr) {
            printf("%c %d \n",node->data,node->wigth);
            printNode(node->left);
            printNode(node->right);
        }

    }
    void replaceMovedElement(HuffmanTreeNode *node) {
        for (int i=0;i<max;i++) {
            if(elementList[i]==nullptr||elementList[i]->moved) {
                elementList[i]=node;
                return;
            }
        }
    }

    /**
     * 获取并设置删除位置，其实用队列实现更佳
     * @return
     */
    int takeAndRemoveMiniData() {
        int minIndex=-1;
        for(int i=0;i<max;i++) {
            HuffmanTreeNode *tree_node = elementList[i];
            if(tree_node!=nullptr && !tree_node->moved) {
                if(minIndex==-1) {
                    minIndex = i;
                }else {
                    HuffmanTreeNode *min_tree_node = elementList[minIndex];
                    if(min_tree_node->wigth>tree_node->wigth) {
                        minIndex = i;
                    }
                }
            }
        }
        if(minIndex!=-1) {
            elementList[minIndex]->moved=true;
        }
        return minIndex;
    }
};

// int main(int argc, char *argv[]) {
//     HuffmanTree *huffman_tree = new HuffmanTree();
//     huffman_tree->appendElemet('A',80);
//     huffman_tree->appendElemet('B',11);
//     huffman_tree->appendElemet('C',6);
//     huffman_tree->appendElemet('D',3);
//     huffman_tree->transToHuffmanTree();
//     huffman_tree->printNode();
//     huffman_tree->decodeTree();
//     huffman_tree->printEncode();
//     char *strs = "AAAACADBAA";
//     String result = huffman_tree->encodeStr(strs);
//     std::cout<<result<<endl;
// }
